SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Root-finding algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Root-finding algorithm</span></span>

</h1>

</header>

<p>In <a href="Numerical_analysis" title="Numerical analysis">numerical analysis</a>, a <b>root-finding algorithm</b> is an <a href="Algorithm" title="Algorithm">algorithm</a> for finding <a href="Zero_of_a_function" title="Zero of a function">zeros</a>, also called "roots", of <a href="Continuous_function" title="Continuous function">continuous functions</a>. A <a href="Zero_of_a_function" title="Zero of a function">zero of a function</a> <span class="texhtml"><i>f</i></span> is a number <span class="texhtml"><i>x</i></span> such that <span class="texhtml"><i>f</i>(<i>x</i>) = 0</span>. As, generally, the zeros of a function cannot be computed exactly nor expressed in <a href="Closed_form_expression" class="mw-redirect" title="Closed form expression">closed form</a>, root-finding algorithms provide approximations to zeros. For functions from the <a href="Real_number" title="Real number">real numbers</a> to real numbers or from the <a href="Complex_number" title="Complex number">complex numbers</a> to the complex numbers, these are expressed either as <a href="Floating-point_arithmetic" title="Floating-point arithmetic">floating-point</a> numbers without error bounds or as floating-point values together with error bounds. The latter, approximations with error bounds, are equivalent to small isolating <a href="Interval_(mathematics)" title="Interval (mathematics)">intervals</a> for real roots or <a href="Disk_(mathematics)" title="Disk (mathematics)">disks</a> for complex roots.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p><a href="Equation_solving" title="Equation solving">Solving an equation</a> <span class="texhtml"><i>f</i>(<i>x</i>) = <i>g</i>(<i>x</i>)</span> is the same as finding the roots of the function <span class="texhtml"><i>h</i>(<i>x</i>) = <i>f</i>(<i>x</i>) – <i>g</i>(<i>x</i>)</span>. Thus root-finding algorithms can be used to solve any <a href="Equation_(mathematics)" class="mw-redirect" title="Equation (mathematics)">equation</a> of continuous functions. However, most root-finding algorithms do not guarantee that they will find all roots of a function, and if such an algorithm does not find any root, that does not necessarily mean that no root exists.

</p><p>Most numerical root-finding methods are <a href="Iterative_method" title="Iterative method">iterative methods</a>, producing a <a href="Sequence" title="Sequence">sequence</a> of numbers that ideally converges towards a root as a <a href="Limit_of_a_sequence" title="Limit of a sequence">limit</a>. They require one or more <i>initial guesses</i> of the root as starting values, then each iteration of the algorithm produces a successively more accurate approximation to the root. Since the iteration must be stopped at some point, these methods produce an approximation to the root, not an exact solution. Many methods compute subsequent values by evaluating an auxiliary function on the preceding values. The limit is thus a <a href="Fixed_point_(mathematics)" title="Fixed point (mathematics)">fixed point</a> of the auxiliary function, which is chosen for having the roots of the original equation as fixed points and for converging rapidly to these fixed points.

</p><p>The behavior of general root-finding algorithms is studied in <a href="Numerical_analysis" title="Numerical analysis">numerical analysis</a>. However, for polynomials specifically, the study of root-finding algorithms belongs to <a href="Computer_algebra" title="Computer algebra">computer algebra</a>, since algebraic properties of polynomials are fundamental for the most efficient algorithms. The efficiency and applicability of an algorithm may depend sensitively on the characteristics of the given functions. For example, many algorithms use the <a href="Derivative" title="Derivative">derivative</a> of the input function, while others work on every <a href="Continuous_function" title="Continuous function">continuous function</a>. In general, numerical algorithms are not guaranteed to find all the roots of a function, so failing to find a root does not prove that there is no root. However, for <a href="Polynomial" title="Polynomial">polynomials</a>, there are specific algorithms that use algebraic properties for certifying that no root is missed and for locating the roots in separate intervals (or disks for complex roots) that are small enough to ensure the convergence of numerical methods (typically <a href="Newton's_method" title="Newton's method">Newton's method</a>) to the unique root within each interval (or disk).

</p>

<div class="mw-heading mw-heading2"><h2 id="Bracketing_methods">Bracketing methods</h2></div>

<p>Bracketing methods determine successively smaller intervals (brackets) that contain a root. When the interval is small enough, then a root is considered found. These generally use the <a href="Intermediate_value_theorem" title="Intermediate value theorem">intermediate value theorem</a>, which asserts that if a continuous function has values of opposite signs at the end points of an interval, then the function has at least one root in the interval. Therefore, they require starting with an interval such that the function takes opposite signs at the end points of the interval. However, in the case of <a href="Polynomial" title="Polynomial">polynomials</a> there are other methods such as <a href="Descartes'_rule_of_signs" title="Descartes' rule of signs">Descartes' rule of signs</a>, <a href="Budan's_theorem" title="Budan's theorem">Budan's theorem</a> and <a href="Sturm's_theorem" title="Sturm's theorem">Sturm's theorem</a> for bounding or determining the number of roots in an interval. They lead to efficient algorithms for <a href="Real-root_isolation" title="Real-root isolation">real-root isolation</a> of polynomials, which find all real roots with a guaranteed accuracy.

</p>

<div class="mw-heading mw-heading3"><h3 id="Bisection_method">Bisection method</h3></div>

<p>The simplest root-finding algorithm is the <a href="Bisection_method" title="Bisection method">bisection method</a>. Let <span class="texhtml"><i>f</i></span> be a <a href="Continuous_function" title="Continuous function">continuous function</a> for which one knows an interval <span class="texhtml">[<i>a</i>, <i>b</i>]</span> such that <span class="texhtml"><i>f</i>(<i>a</i>)</span> and <span class="texhtml"><i>f</i>(<i>b</i>)</span> have opposite signs (a bracket). Let <span class="texhtml"><i>c</i> = (<i>a</i> + <i>b</i>)/2</span> be the middle of the interval (the midpoint or the point that bisects the interval). Then either <span class="texhtml"><i>f</i>(<i>a</i>)</span> and <span class="texhtml"><i>f</i>(<i>c</i>)</span>, or <span class="texhtml"><i>f</i>(<i>c</i>)</span> and <span class="texhtml"><i>f</i>(<i>b</i>)</span> have opposite signs, and one has divided by two the size of the interval. Although the bisection method is robust, it gains one and only one <a href="Bit" title="Bit">bit</a> of accuracy with each iteration. Therefore, the number of function evaluations required for finding an <i>ε</i>-approximate root is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}{\frac {b-a}{\varepsilon }}}">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}{\frac {b-a}{\varepsilon }}}</annotation>

</semantics>

</math></span><img src="./363c8ad19266ae04e84dcee9859f016ba7e7d295.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:10.317ex; height:5.343ex;" alt="{\displaystyle \log _{2}{\frac {b-a}{\varepsilon }}}" loading="lazy"></span>. Other methods, under appropriate conditions, can gain accuracy faster.

</p>

<div class="mw-heading mw-heading3"><h3 id="False_position_(regula_falsi)">False position (<i>regula falsi</i>)</h3></div>

<p>The <a href="False_position_method" class="mw-redirect" title="False position method">false position method</a>, also called the <i>regula falsi</i> method, is similar to the bisection method, but instead of using bisection search's middle of the interval it uses the <a href="X-intercept" class="mw-redirect" title="X-intercept"><span class="texhtml"><i>x</i></span>-intercept</a> of the line that connects the plotted function values at the endpoints of the interval, that is

</p>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c={\frac {af(b)-bf(a)}{f(b)-f(a)}}.}</annotation>

</semantics>

</math></span><img src="./dfee15e52fafd3b28dd9f0a1d65d79a52a615f8f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:19.059ex; height:6.509ex;" alt="{\displaystyle c={\frac {af(b)-bf(a)}{f(b)-f(a)}}.}" loading="lazy"></span></dd></dl>

<p>False position is similar to the <a href="Secant_method" title="Secant method">secant method</a>, except that, instead of retaining the last two points, it makes sure to keep one point on either side of the root. The false position method can be faster than the bisection method and will never diverge like the secant method. However, it may fail to converge in some naive implementations due to roundoff errors that may lead to a wrong sign for <span class="texhtml"><i>f</i>(<i>c</i>)</span>. Typically, this may occur if the <a href="Derivative" title="Derivative">derivative</a> of <span class="texhtml mvar" style="font-style:italic;">f</span> is large in the neighborhood of the root.

</p>

<div class="mw-heading mw-heading2"><h2 id="Interpolation">Interpolation</h2></div>

<p>Many root-finding processes work by <a href="Interpolation" title="Interpolation">interpolation</a>. This consists in using the last computed approximate values of the root for approximating the function by a <a href="Polynomial" title="Polynomial">polynomial</a> of low degree, which takes the same values at these approximate roots. Then the root of the polynomial is computed and used as a new approximate value of the root of the function, and the process is iterated.

</p><p>Interpolating two values yields a line: a polynomial of degree one. This is the basis of the <a href="Secant_method" title="Secant method">secant method</a>. <i>Regula falsi</i> is also an interpolation method that interpolates two points at a time but it differs from the secant method by using two points that are not necessarily the last two computed points. Three values define a parabolic curve: a <a href="Quadratic_function" title="Quadratic function">quadratic function</a>. This is the basis of <a href="Muller's_method" title="Muller's method">Muller's method</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Iterative_methods">Iterative methods</h2></div>

<p>Although all root-finding algorithms proceed by <a href="Iteration" title="Iteration">iteration</a>, an <a href="Iterative_method" title="Iterative method">iterative</a> root-finding method generally uses a specific type of iteration, consisting of defining an auxiliary function, which is applied to the last computed approximations of a root for getting a new approximation. The iteration stops when a <a href="Fixed-point_iteration" title="Fixed-point iteration">fixed point</a> of the auxiliary function is reached to the desired precision, i.e., when a new computed value is sufficiently close to the preceding ones.

</p>

<div class="mw-heading mw-heading3"><h3 id="Newton's_method_(and_similar_derivative-based_methods)">Newton's method (and similar derivative-based methods)</h3></div>

<p><a href="Newton's_method" title="Newton's method">Newton's method</a> assumes the function <i>f</i> to have a continuous <a href="Derivative" title="Derivative">derivative</a>. Newton's method may not converge if started too far away from a root. However, when it does converge, it is faster than the bisection method; its <a href="Order_of_convergence" class="mw-redirect" title="Order of convergence">order of convergence</a> is usually quadratic whereas the bisection method's is linear. Newton's method is also important because it readily generalizes to higher-dimensional problems. <a href="Householder's_method" title="Householder's method">Householder's methods</a> are a class of Newton-like methods with higher orders of convergence. The first one after Newton's method is <a href="Halley's_method" title="Halley's method">Halley's method</a> with cubic order of convergence.

</p>

<div class="mw-heading mw-heading3"><h3 id="Secant_method">Secant method</h3></div>

<p>Replacing the derivative in Newton's method with a <a href="Finite_difference" title="Finite difference">finite difference</a>, we get the <a href="Secant_method" title="Secant method">secant method</a>. This method does not require the computation (nor the existence) of a derivative, but the price is slower convergence (the order of convergence is the <a href="Golden_ratio" title="Golden ratio">golden ratio</a>, approximately 1.62<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>). A generalization of the secant method in higher dimensions is <a href="Broyden's_method" title="Broyden's method">Broyden's method</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Steffensen's_method">Steffensen's method</h3></div>

<p>If we use a polynomial fit to remove the quadratic part of the finite difference used in the secant method, so that it better approximates the derivative, we obtain <a href="Steffensen's_method" title="Steffensen's method">Steffensen's method</a>, which has quadratic convergence, and whose behavior (both good and bad) is essentially the same as Newton's method but does not require a derivative.

</p>

<div class="mw-heading mw-heading3"><h3 id="Fixed_point_iteration_method">Fixed point iteration method</h3></div>

<p>We can use the <a href="Fixed-point_iteration" title="Fixed-point iteration">fixed-point iteration</a> to find the root of a function. Given a function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math></span><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"></span> which we have set to zero to find the root (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=0}</annotation>

</semantics>

</math></span><img src="./cf85883d74b75fe35ca8d3f2b44802df078e4fa1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.678ex; height:2.843ex;" alt="{\displaystyle f(x)=0}" loading="lazy"></span>), we rewrite the equation in terms of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> so that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=0}</annotation>

</semantics>

</math></span><img src="./cf85883d74b75fe35ca8d3f2b44802df078e4fa1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.678ex; height:2.843ex;" alt="{\displaystyle f(x)=0}" loading="lazy"></span> becomes <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=g(x)}</annotation>

</semantics>

</math></span><img src="./608bf2758bdb761cb78a3104f6a8467613c8b449.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.683ex; height:2.843ex;" alt="{\displaystyle x=g(x)}" loading="lazy"></span> (note, there are often many <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation>

</semantics>

</math></span><img src="./c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}" loading="lazy"></span> functions for each <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=0}</annotation>

</semantics>

</math></span><img src="./cf85883d74b75fe35ca8d3f2b44802df078e4fa1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.678ex; height:2.843ex;" alt="{\displaystyle f(x)=0}" loading="lazy"></span> function). Next, we relabel each side of the equation as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{n+1}=g(x_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n+1}=g(x_{n})}</annotation>

</semantics>

</math></span><img src="./b48bb2d31c5d71c60cbfee31ec378c833bb4c7ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.221ex; height:2.843ex;" alt="{\displaystyle x_{n+1}=g(x_{n})}" loading="lazy"></span> so that we can perform the iteration. Next, we pick a value for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}}</annotation>

</semantics>

</math></span><img src="./a8788bf85d532fa88d1fb25eff6ae382a601c308.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{1}}" loading="lazy"></span> and perform the iteration until it converges towards a root of the function. If the iteration converges, it will converge to a root. The iteration will only converge if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |g'(root)|<1}">

</mrow>

<msup>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |g'(root)|<1}</annotation>

</semantics>

</math></span><img src="./e72ed01b48be0f78bea75e50a39c992d0a02b94e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.31ex; height:3.009ex;" alt="{\displaystyle |g'(root)|<1}" loading="lazy"></span>.

</p><p>As an example of converting <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=0}</annotation>

</semantics>

</math></span><img src="./cf85883d74b75fe35ca8d3f2b44802df078e4fa1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.678ex; height:2.843ex;" alt="{\displaystyle f(x)=0}" loading="lazy"></span> to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x=g(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=g(x)}</annotation>

</semantics>

</math></span><img src="./608bf2758bdb761cb78a3104f6a8467613c8b449.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.683ex; height:2.843ex;" alt="{\displaystyle x=g(x)}" loading="lazy"></span>, if given the function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=x^{2}+x-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=x^{2}+x-1}</annotation>

</semantics>

</math></span><img src="./20ed204c4988c0bdc01e615f072545bb5f7c7668.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.073ex; height:3.176ex;" alt="{\displaystyle f(x)=x^{2}+x-1}" loading="lazy"></span>, we will rewrite it as one of the following equations.

</p>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n+1}=(1/x_{n})-1}</annotation>

</semantics>

</math></span><img src="./16359c6d5576f7036b2e184bf2364e037dd4a7cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.432ex; height:2.843ex;" alt="{\displaystyle x_{n+1}=(1/x_{n})-1}" loading="lazy"></span>,</dd>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n+1}=1/(x_{n}+1)}</annotation>

</semantics>

</math></span><img src="./e7f1b84d2b1779a62561e0d474e40ab6367e2d87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.432ex; height:2.843ex;" alt="{\displaystyle x_{n+1}=1/(x_{n}+1)}" loading="lazy"></span>,</dd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n+1}=1-x_{n}^{2}}</annotation>

</semantics>

</math></span><img src="./b7632d9fd84ee0d367ca97f86319c1f0c8522a11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.298ex; height:2.843ex;" alt="{\displaystyle x_{n+1}=1-x_{n}^{2}}" loading="lazy"></span>,</dd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n+1}=x_{n}^{2}+2x_{n}-1}</annotation>

</semantics>

</math></span><img src="./f751ba8f2987c34ccba9ac0b69fcf969d4aedf83.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.849ex; height:2.843ex;" alt="{\displaystyle x_{n+1}=x_{n}^{2}+2x_{n}-1}" loading="lazy"></span>, or</dd>

<msub>

</mrow>

</msub>

<msqrt>

<msub>

</mrow>

</msub>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{n+1}=\pm {\sqrt {1-x_{n}}}}</annotation>

</semantics>

</math></span><img src="./bb914b53b16be6c33ed36aabbdef63451b67272e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:18.43ex; height:3.509ex;" alt="{\displaystyle x_{n+1}=\pm {\sqrt {1-x_{n}}}}" loading="lazy"></span>.</dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Inverse_interpolation">Inverse interpolation</h3></div>

<p>The appearance of complex values in interpolation methods can be avoided by interpolating the <a href="Inverse_function" title="Inverse function">inverse</a> of <i>f</i>, resulting in the <a href="Inverse_quadratic_interpolation" title="Inverse quadratic interpolation">inverse quadratic interpolation</a> method. Again, convergence is asymptotically faster than the secant method, but inverse quadratic interpolation often behaves poorly when the iterates are not close to the root.

</p>

<div class="mw-heading mw-heading2"><h2 id="Combinations_of_methods">Combinations of methods</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Brent's_method">Brent's method</h3></div>

<p><a href="Brent's_method" title="Brent's method">Brent's method</a> is a combination of the bisection method, the secant method and <a href="Inverse_quadratic_interpolation" title="Inverse quadratic interpolation">inverse quadratic interpolation</a>. At every iteration, Brent's method decides which method out of these three is likely to do best, and proceeds by doing a step according to that method. This gives a robust and fast method, which therefore enjoys considerable popularity.

</p>

<div class="mw-heading mw-heading3"><h3 id="Ridders'_method">Ridders' method</h3></div>

<p><a href="Ridders'_method" title="Ridders' method">Ridders' method</a> is a hybrid method that uses the value of function at the midpoint of the interval to perform an exponential interpolation to the root. This gives a fast convergence with a guaranteed convergence of at most twice the number of iterations as the bisection method.

</p>

<div class="mw-heading mw-heading2"><h2 id="Roots_of_polynomials">Roots of polynomials </h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .excerpt-hat .mw-editsection-like{font-style:normal}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236090951">

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable dablink excerpt-hat selfref">This section is an excerpt from <a href="Polynomial_root-finding" title="Polynomial root-finding">Polynomial root-finding</a>.<span class="mw-editsection-like "><span class="mw-editsection-bracket">[</span><a class="external text external" href="https://en.wikipedia.org/w/index.php?title=Polynomial_root-finding&action=edit">edit</a><span class="mw-editsection-bracket">]</span></span></div><div class="excerpt">

<p>Finding <a href="Polynomial_root" class="mw-redirect" title="Polynomial root">the roots of polynomials</a> is a long-standing problem that has been extensively studied throughout the history and substantially influenced the development of mathematics. It involves determining either a numerical approximation or a closed-form expression of the roots of a univariate polynomial, i.e., determining approximate or closed form solutions of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n}=0}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n}=0}</annotation>

</semantics>

</math></span><img src="./238f3460ac29daf8d21bb1da3454db12356b131e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:33.908ex; height:3.009ex;" alt="{\displaystyle a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n}=0}" loading="lazy"></span>

</p><p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}}</annotation>

</semantics>

</math></span><img src="./0bc77764b2e74e64a63341054fa90f3e07db275f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.029ex; height:2.009ex;" alt="{\displaystyle a_{i}}" loading="lazy"></span> are either <a href="Real_number" title="Real number">real</a> or <a href="Complex_number" title="Complex number">complex numbers</a>.

</p><p>Efforts to understand and solve polynomial equations led to the development of important mathematical concepts, including <a href="Irrational_number" title="Irrational number">irrational</a> and complex numbers, as well as foundational structures in modern algebra such as <a href="Field_(mathematics)" title="Field (mathematics)">fields</a>, <a href="Ring_(mathematics)" title="Ring (mathematics)">rings</a>, and <a href="Group_(mathematics)" title="Group (mathematics)">groups</a>.

</p>

Despite being historically important, finding the roots of higher degree polynomials no longer play a central role in mathematics and computational mathematics, with one major exception in <a href="Computer_algebra" title="Computer algebra">computer algebra</a>.<sup id="cite_ref-Polynomial_root-finding_:1_3-0" class="reference"><a href="#cite_note-Polynomial_root-finding_:1-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></div></div>

<div class="mw-heading mw-heading2"><h2 id="Finding_roots_in_higher_dimensions">Finding roots in higher dimensions</h2></div>

<p>The <a href="Bisection_method" title="Bisection method">bisection method</a> has been generalized to higher dimensions; these methods are called <b>generalized bisection methods</b>.<sup id="cite_ref-:0_4-0" class="reference"><a href="#cite_note-:0-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> At each iteration, the domain is partitioned into two parts, and the algorithm decides - based on a small number of function evaluations - which of these two parts must contain a root. In one dimension, the criterion for decision is that the function has opposite signs. The main challenge in extending the method to multiple dimensions is to find a criterion that can be computed easily and guarantees the existence of a root.

</p><p>The <a href="Poincar%C3%A9%E2%80%93Miranda_theorem" title="Poincaré–Miranda theorem">Poincaré–Miranda theorem</a> gives a criterion for the existence of a root in a rectangle, but it is hard to verify because it requires evaluating the function on the entire boundary of the rectangle.

</p><p>Another criterion is given by a theorem of <a href="Leopold_Kronecker" title="Leopold Kronecker">Kronecker</a>.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> It says that, if the <a href="Degree_of_a_continuous_mapping" title="Degree of a continuous mapping">topological degree</a> of a function <i>f</i> on a rectangle is non-zero, then the rectangle must contain at least one root of <i>f</i>. This criterion is the basis for several root-finding methods, such as those of Stenger<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> and Kearfott.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> However, computing the topological degree can be time-consuming.

</p><p>A third criterion is based on a <i>characteristic polyhedron</i>. This criterion is used by a method called Characteristic Bisection.<sup id="cite_ref-:0_4-1" class="reference"><a href="#cite_note-:0-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 19--">: 19-- </span></sup> It does not require computing the topological degree; it only requires computing the signs of function values. The number of required evaluations is at least <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}(D/\epsilon )}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}(D/\epsilon )}</annotation>

</semantics>

</math></span><img src="./fe93a7260f7eee9f52c21df299a79ddc9c37f0bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.866ex; height:2.843ex;" alt="{\displaystyle \log _{2}(D/\epsilon )}" loading="lazy"></span>, where <i>D</i> is the length of the longest edge of the characteristic polyhedron.<sup id="cite_ref-:2_9-0" class="reference"><a href="#cite_note-:2-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 11, Lemma.4.7">: 11, Lemma.4.7 </span></sup> Note that Vrahatis and Iordanidis <sup id="cite_ref-:2_9-1" class="reference"><a href="#cite_note-:2-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> prove a lower bound on the number of evaluations, and not an upper bound.

</p><p>A fourth method uses an <a href="Intermediate_value_theorem" title="Intermediate value theorem">intermediate value theorem</a> on simplices.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> Again, no upper bound on the number of queries is given.

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}

/* end https://en.wikipedia.org/ */

</style><div class="div-col">

<ul><li><a href="List_of_root_finding_algorithms" class="mw-redirect" title="List of root finding algorithms">List of root finding algorithms</a></li>

<li><a href="Fixed-point_computation" title="Fixed-point computation">Fixed-point computation</a></li></ul>

<p><a href="Broyden's_method" title="Broyden's method">Broyden's method</a> – Quasi-Newton root-finding method for the multivariable case

</p>

<ul><li><a href="Cryptographically_secure_pseudorandom_number_generator" title="Cryptographically secure pseudorandom number generator">Cryptographically secure pseudorandom number generator</a> – Type of functions designed for being unsolvable by root-finding algorithms</li>

<li><a href="GNU_Scientific_Library" title="GNU Scientific Library">GNU Scientific Library</a></li>

<li><a href="Graeffe's_method" title="Graeffe's method">Graeffe's method</a> – Algorithm for finding polynomial roots</li>

<li><a href="Lill's_method" title="Lill's method">Lill's method</a> – Graphical method for the real roots of a polynomial</li>

<li><a href="MPSolve" title="MPSolve">MPSolve</a> – Software for approximating the roots of a polynomial with arbitrarily high precision</li>

<li><a href="Multiplicity_(mathematics)" title="Multiplicity (mathematics)">Multiplicity (mathematics)</a> – Number of times an object must be counted for making true a general formula</li>

<li><a href="Nth_root_algorithm" class="mw-redirect" title="Nth root algorithm"><span class="texhtml"><i>n</i></span>th root algorithm</a></li>

<li><a href="System_of_polynomial_equations" title="System of polynomial equations">System of polynomial equations</a> – Roots of multiple multivariate polynomials</li>

<li><a href="Kantorovich_theorem" title="Kantorovich theorem">Kantorovich theorem</a> – About the convergence of Newton's method</li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFPressTeukolskyVetterlingFlannery2007" class="citation book cs1">Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). <a rel="nofollow" class="external text" href="http://apps.nrbook.com/empanel/index.html#pg=442">"Chapter 9. Root Finding and Nonlinear Sets of Equations"</a>. <i>Numerical Recipes: The Art of Scientific Computing</i> (3rd ed.). New York: Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-88068-8</bdi>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFChanson2024" class="citation web cs1">Chanson, Jeffrey R. (October 3, 2024). <a rel="nofollow" class="external text" href="https://math.libretexts.org/Bookshelves/Applied_Mathematics/Numerical_Methods_(Chasnov)/02%3A_Root_Finding/2.04%3A_Order_of_Convergence">"Order of Convergence"</a>. <i>LibreTexts Mathematics</i><span class="reference-accessdate">. Retrieved <span class="nowrap">October 3,</span> 2024</span>.</cite></span>

</li>

<li id="cite_note-Polynomial_root-finding_:1-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-Polynomial_root-finding_:1_3-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFPan1997" class="citation journal cs1">Pan, Victor Y. (January 1997). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://epubs.siam.org/doi/10.1137/S0036144595288554">"Solving a Polynomial Equation: Some History and Recent Progress"</a></span>. <i>SIAM Review</i>. <b>39</b> (2): <span class="nowrap">187–</span>220. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0036144595288554">10.1137/S0036144595288554</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0036-1445">0036-1445</a>.</cite></span>

</li>

<li id="cite_note-:0-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_4-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFMourrainVrahatisYakoubsohn2002" class="citation journal cs1">Mourrain, B.; Vrahatis, M. N.; Yakoubsohn, J. C. (2002-06-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcom.2001.0636">"On the Complexity of Isolating Real Roots and Computing with Certainty the Topological Degree"</a>. <i>Journal of Complexity</i>. <b>18</b> (2): <span class="nowrap">612–</span>640. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcom.2001.0636">10.1006/jcom.2001.0636</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0885-064X">0885-064X</a>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFVrahatis2020" class="citation book cs1">Vrahatis, Michael N. (2020). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/978-3-030-40616-5_17">"Generalizations of the Intermediate Value Theorem for Approximating Fixed Points and Zeros of Continuous Functions"</a>. In Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.). <i>Numerical Computations: Theory and Algorithms</i>. Lecture Notes in Computer Science. Vol. 11974. Cham: Springer International Publishing. pp. <span class="nowrap">223–</span>238. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-40616-5_17">10.1007/978-3-030-40616-5_17</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-030-40616-5</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:211160947">211160947</a>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFOrtegaRheinboldt2000" class="citation book cs1">Ortega, James M.; Rheinboldt, Werner C. (2000). <i>Iterative solution of nonlinear equations in several variables</i>. Society for Industrial and Applied Mathematics. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89871-461-6</bdi>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFStenger1975" class="citation journal cs1">Stenger, Frank (1975-03-01). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF01419526">"Computing the topological degree of a mapping inRn"</a></span>. <i>Numerische Mathematik</i>. <b>25</b> (1): <span class="nowrap">23–</span>38. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01419526">10.1007/BF01419526</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0945-3245">0945-3245</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:122196773">122196773</a>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFKearfott1979" class="citation journal cs1">Kearfott, Baker (1979-06-01). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF01404868">"An efficient degree-computation method for a generalized method of bisection"</a></span>. <i>Numerische Mathematik</i>. <b>32</b> (2): <span class="nowrap">109–</span>127. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01404868">10.1007/BF01404868</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0029-599X">0029-599X</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:122058552">122058552</a>.</cite></span>

</li>

<li id="cite_note-:2-9"><span class="mw-cite-backlink">^ <a href="#cite_ref-:2_9-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:2_9-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFVrahatisIordanidis1986" class="citation journal cs1">Vrahatis, M. N.; Iordanidis, K. I. (1986-03-01). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF01389620">"A Rapid Generalized Method of Bisection for Solving Systems of Non-linear Equations"</a></span>. <i>Numerische Mathematik</i>. <b>49</b> (2): <span class="nowrap">123–</span>138. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01389620">10.1007/BF01389620</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0945-3245">0945-3245</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:121771945">121771945</a>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFVrahatis2020" class="citation journal cs1">Vrahatis, Michael N. (2020-04-15). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.topol.2019.107036">"Intermediate value theorem for simplices for simplicial approximation of fixed points and zeros"</a>. <i>Topology and Its Applications</i>. <b>275</b>: 107036. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.topol.2019.107036">10.1016/j.topol.2019.107036</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0166-8641">0166-8641</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:213249321">213249321</a>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li>Victor Yakovlevich Pan: "Solving a Polynomial Equation: Some History and Recent Progress", SIAM Review, Vol.39, No.2, pp.187-220 (June, 1997).</li>

<li>John Michael McNamee: <i>Numerical Methods for Roots of Polynomials - Part I</i>, Elsevier, ISBN 978-0-444-52729-5 (2007).</li>

<li>John Michael McNamee and Victor Yakovlevich Pan: <i>Numerical Methods for Roots of Polynomials - Part II</i>, Elsevier, ISBN 978-0-444-52730-1 (2013).</li></ul>

<p><br>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Root-finding_algorithms311" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Root-finding_algorithms311" style="font-size:114%;margin:0 4em"></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a class="mw-selflink-fragment" href="#Bracketing_methods">Bracketing (no derivative)</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Bisection_method" title="Bisection method">Bisection method</a></li>

<li><a href="Regula_falsi" title="Regula falsi">Regula falsi</a></li>

<li><a href="ITP_method" title="ITP method">ITP method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Householder's_method" title="Householder's method">Householder</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Newton's_method" title="Newton's method">Newton's method</a></li>

<li><a href="Halley's_method" title="Halley's method">Halley's method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quasi-Newton_method" title="Quasi-Newton method">Quasi-Newton</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Broyden's_method" title="Broyden's method">Broyden's method</a></li>

<li><a href="Secant_method" title="Secant method">Secant method</a></li>

<li><a href="Newton%E2%80%93Krylov_method" title="Newton–Krylov method">Newton–Krylov method</a></li>

<li><a href="Steffensen's_method" title="Steffensen's method">Steffensen's method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a class="mw-selflink-fragment" href="#Combinationations_of_methods">Hybrid methods</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Brent's_method" title="Brent's method">Brent's method</a></li>

<li><a href="Ridders'_method" title="Ridders' method">Ridders' method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Polynomial_root-finding_algorithms" class="mw-redirect" title="Polynomial root-finding algorithms">Polynomial methods</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Aberth_method" title="Aberth method">Aberth method</a></li>

<li><a href="Bairstow's_method" title="Bairstow's method">Bairstow's method</a></li>

<li><a href="Bernoulli's_method" title="Bernoulli's method">Bernoulli's method</a></li>

<li><a href="Durand%E2%80%93Kerner_method" title="Durand–Kerner method">Durand–Kerner method</a></li>

<li><a href="Graeffe's_method" title="Graeffe's method">Graeffe's method</a></li>

<li><a href="Jenkins%E2%80%93Traub_algorithm" title="Jenkins–Traub algorithm">Jenkins–Traub algorithm</a></li>

<li><a href="Lehmer%E2%80%93Schur_algorithm" title="Lehmer–Schur algorithm">Lehmer–Schur algorithm</a></li>

<li><a href="Laguerre's_method" title="Laguerre's method">Laguerre's method</a></li>

<li><a href="Splitting_circle_method" title="Splitting circle method">Splitting circle method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other methods</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Fixed-point_iteration" title="Fixed-point iteration">Fixed-point iteration</a></li>

<li><a href="Inverse_quadratic_interpolation" title="Inverse quadratic interpolation">Inverse quadratic interpolation</a></li>

<li><a href="Muller's_method" title="Muller's method">Muller's method</a></li>

<li><a href="Sidi's_generalized_secant_method" title="Sidi's generalized secant method">Sidi's generalized secant method</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Data_structures_and_algorithms145" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Data_structures_and_algorithms145" style="font-size:114%;margin:0 4em"><a href="Data_structure" title="Data structure">Data structures</a> and <a href="Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Data structures</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Array_(data_structure)" title="Array (data structure)">Array</a></li>

<li><a href="Associative_array" title="Associative array">Associative array</a></li>

<li><a href="Binary_search_tree" title="Binary search tree">Binary search tree</a></li>

<li><a href="Fenwick_tree" title="Fenwick tree">Fenwick tree</a></li>

<li><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graph</a></li>

<li><a href="Hash_table" title="Hash table">Hash table</a></li>

<li><a href="Linked_list" title="Linked list">Linked list</a></li>

<li><a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a></li>

<li><a href="Segment_tree" title="Segment tree">Segment tree</a></li>

<li><a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li>

<li><a href="String_(computer_science)" title="String (computer science)">String</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Algorithms and <a href="Algorithmic_paradigm" title="Algorithmic paradigm">algorithmic paradigms</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Backtracking" title="Backtracking">Backtracking</a></li>

<li><a href="Binary_search" title="Binary search">Binary search</a></li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a></li>

<li><a href="Brute-force_search" title="Brute-force search">Brute-force search</a></li>

<li><a href="Depth-first_search" title="Depth-first search">Depth-first search</a></li>

<li><a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">Divide and conquer</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Graph_traversal" title="Graph traversal">Graph traversal</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy</a></li>

<li><a href="Hash_function" title="Hash function">Hash function</a></li>

<li><a href="Minimax" title="Minimax">Minimax</a></li>

<li><a href="Online_algorithm" title="Online algorithm">Online</a></li>

<li><a href="Randomized_algorithm" title="Randomized algorithm">Randomized</a></li>

<li><a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursion</a></li>

<li><a href="Sorting_algorithm" title="Sorting algorithm">Sorting</a></li>

<li><a href="Streaming_algorithm" title="Streaming algorithm">Streaming</a></li>

<li><a href="Sweep_line_algorithm" title="Sweep line algorithm">Sweep line</a></li>

<li><a href="String-searching_algorithm" title="String-searching algorithm">String-searching</a></li>

<li><a href="Topological_sorting" title="Topological sorting">Topological sorting</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="List_of_data_structures" title="List of data structures">List of data structures</a></li>

<li><a href="List_of_algorithms" title="List of algorithms">List of algorithms</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-15" href="https://en.wikipedia.org/wiki/?title=Root-finding_algorithm&oldid=1300598924">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>